package com.leetcode.p500;

import java.util.HashMap;

public class Test509 {

    HashMap<Integer, Integer> hashMap = new HashMap<>();

    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int n1;
        int n2;
        if (hashMap.containsKey(n - 1)) {
            n1 = hashMap.get(n - 1);
        } else {
            n1 = fib(n - 1);
            hashMap.put(n - 1, n1);
        }

        if (hashMap.containsKey(n - 2)) {
            n2 = hashMap.get(n - 2);
        } else {
            n2 = fib(n - 2);
            hashMap.put(n - 2, n2);
        }

        return n1 + n2;
    }

    public static void main(String[] args) {
        Test509 test = new Test509();
        int result = test.fib(7);
        System.out.println(result);
    }
}
